/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// 这是 ai 的回答
/* 
方法思路
定义状态：设dp[i]为字符串s的前i个字符（即子串s.substring(0, i)）是否可以由字典中的单词拼接而成。
初始化：dp[0] = true，表示空字符串可以由字典中的单词拼接而成（不需要任何单词）。
状态转移方程：对于每个位置i（从 1 到s.length），检查是否存在一个位置j（0 ≤ j < i），使得：
dp[j]为true，即子串s.substring(0, j)可以由字典中的单词拼接而成。
子串s.substring(j, i)存在于字典wordDict中。
如果存在这样的j，则dp[i]为true，否则为false。
结果：dp[s.length]即为所求的结果，表示整个字符串s是否可以由字典中的单词拼接而成。

代码解释
初始化字典集合：将wordDict转换为Set，以便快速查找某个单词是否存在。
创建 DP 数组：创建一个长度为n+1的布尔数组dp，其中dp[i]表示字符串s的前i个字符是否可以由字典中的单词拼接而成。
填充 DP 数组：遍历每个位置i，对于每个i，再遍历所有可能的分割点j，检查子串s.substring(0, j)和s.substring(j, i)是否满足条件。
返回结果：返回dp[n]，即整个字符串s是否可以由字典中的单词拼接而成。
*/
var wordBreak = function (s, wordDict) {
  const n = s.length;
  const wordSet = new Set(wordDict);
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // 空字符串可以被拼接

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
};